package someTestExcemple.huaweiOd.slidingWindow;

//华为OD机试 - 补种未成活胡杨 - 滑动窗口（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/131624189
//典型滑动窗口
/*思路分析
        我们可以使用滑动窗口算法来解决这个问题。具体步骤如下：
        初始化变量：记录当前窗口内未成活胡杨的数量、最大连续胡杨棵数。
        遍历未成活胡杨数组：不断扩大窗口，当窗口内未成活胡杨数量超过可补种数量 K 时，缩小窗口。
        更新最大连续胡杨棵数：在每次窗口变化时，计算当前窗口内的连续胡杨棵数，并更新最大连续胡杨棵数。*/
import java.util.*;
public class ReplantTrees {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取总种植数量
        int N = scanner.nextInt();
        // 读取未成活胡杨数量
        int M = scanner.nextInt();
        int[] deadPoplars = new int[M];
        // 读取未成活胡杨编号
        for (int i = 0; i < M; i++) {
            deadPoplars[i] = scanner.nextInt();
        }
        // 读取最多可补种数量
        int K = scanner.nextInt();
        scanner.close();
        if(K==0) {
            //不能重新补种，要另外考虑
            int maxLen = 0;
            int len =0;
            for(int i=0;i<M;i++) {
                if(i!=0){
                    len = deadPoplars[i] -deadPoplars[i-1]-1;
                } else {
                    len = deadPoplars[i]-1;
                }
                maxLen =Math.max(len,maxLen);
            }
            System.out.println(maxLen);
            return;
        }

        int left = 0;
        int maxLength = 0;
        // 用于记录当前窗口内未成活胡杨的数量
        int count = 0;

        // 右指针遍历未成活胡杨数组
        for (int right = 0; right < M; right++) {
            // 每遇到一棵未成活胡杨，计数加 1
            count++;

            // 当窗口内未成活胡杨数量超过可补种数量时，缩小窗口
            while (count > K) {
                // 左指针右移，意味着放弃补种左指针指向的未成活胡杨
                left++;
                // 未成活胡杨计数减 1
                count--;
            }

            // 计算当前连续胡杨的数量
            //todo 充分考虑边界条件
            int currentLength;
            if (left == 0) {
                // 如果左指针在起始位置,此时的left位置上是种了树
                currentLength = deadPoplars[right] + deadPoplars[left];
            } else {
                //left左移过，此时delft[left] 没种树，deadPoplars[0-left]的位置都没种树
                //此时窗口内连续胡杨数量
                if(left != right) {
                    currentLength = (deadPoplars[right] - deadPoplars[left] +1) - 1;
                } else {
                    currentLength = (deadPoplars[right] -deadPoplars[right-1] +1)-1;
                }
            }
            // 更新最大连续胡杨数量
            maxLength = Math.max(maxLength, currentLength);
        }

        System.out.println(maxLength);
    }
}
